1. Field
This invention relates to printing systems using digital halftoning, more particularly to printing systems using digital halftoning with error diffusion.
2. Background
Digital printers receive image data structured as a series of digital numbers that represent spatial samples of an analog image. Typically, there is a corresponding relationship between these samples and the physical dots to be printed. For example, a 600 dots-per-inch (dpi) printer will have 600 samples of data per lineal inch of the physical substrate, or a 600×600 square grid of samples to cover a square inch of the substrate (when producing a monochrome image). Each sample is represented via a predetermined number of bits, which determine the available shades of gray for the printer. An 8-bit sample, for example, can represent values between 0 and 255, which in turn can represent 0% coverage (i.e., no ink, toner, dye etc. is deposited at this location) and maximum coverage (the maximum physically realizable amount of ink, toner, dye etc. is deposited) respectively.
Some digital printers are capable of outputting varying amounts of their colorant material, from none up to a maximum density. “Bitonal” digital printers can only print a dot of a single density at each sample position, referred to as picture elements (pixels) on the printed image, or print nothing at said dot position. The simplest bitonal printers in the prior art have used a threshold to determine whether a dot is printed. At each sample location, if the value of the sample is above the threshold, the dot is printed. If the value of the sample is below the threshold, the dot is not printed. The threshold may be constant over the whole image, or may be variable based on position or other methods as practiced in the prior art.
This approach may lead to inaccurate images, since the actual values printed correspond to either 0, when no dot is printed, or 255 when a dot is printed. This assumes an 8-bit value for each sample. The actual value of the pixel may have been much different. For example, the threshold may be set at the pixel value 128. If a pixel has a value of 127, no dot is printed. The error between the actual value printed, 0, and the value desired 127, is fairly large. This can lead to discontinuities and artifacts in the printed image.
A prior-art technique referred to as error diffusion offers a solution to this problem. The difference between actual printed and desired values is divided up and passed on to neighboring pixels, in what will be referred to as standard error diffusion. Using the example above, the error value of 127 will be passed or diffused to neighboring pixels yet to be rendered in the processing stream. Typically, neighboring pixels receive a set proportion of the error value. A typical scheme is to assign the value in proportions of 1/16, 3/16, 5/16 and 7/16. In this example, the value of 127 would be multiplied by these ratios and the resulting number would be added to the desired pixel value for the neighboring pixel.
If the error value were 8 and the desired pixel value were 121, the resulting pixel value would be 129. Note that this pixel would have a dot printed after the addition of the error value whereas it would not have had one printed without the error. This approach is referred to as standard, or Floyd-Steinberg, error diffusion. The error is pushed from the current pixel to subsequent pixels. This approach was originally disclosed in by R. W. Floyd and L. Steinberg in “An Adaptive Algorithm for Spatial Grayscale,” Proceedings of the Society for Information Display, vol. 17, no. 2, pp. 75-77, 1976.
An alternative error diffusion algorithm is referred to as back error compensation. In this method, the error value is computed by summing weighted values already computed at pixel locations previously processed. The summation results in an error value added to the desired value. The resulting value is then used to print a dot or not, and an error value is computed for that pixel and stored. In this approach, the error value for a given pixel is pulled from neighboring pixels.
These two approaches have been demonstrated to be mathematically equivalent. Other variations of each of these approaches are well known in the art. The detailed behavior of the dot patterns produced by these methods depends upon the initial error values, referred to herein as seed values.
If the image is monochrome, there will only be one set of seed values, those necessary to provide values for the process used to compute the error value. For color systems, there will be a set for each color, typically cyan (C), magenta (M), yellow (Y), and black (K). Alternatively, some systems use only CMY.
As discussed above, the current pixel value is a sum of the error value and the desired pixel value. The error value is either pushed to subsequent pixels or pulled from previous pixels. The process used to compute the current pixel value, that value that will actually be compared to the threshold, does not vary even if there are no previous pixels from which to obtain error values. These pixels use the seed values as their error values.
The first part of the printed image processed will be heavily influenced by the values of these seed values. They will affect the initial phase of the resulting dot pattern in the halftone image. This is especially true when a large uniform light area exists at the first part processed. A quasi-periodic artifact could appear in this area, because of phased-locked output patterns. Another difficulty can occur as coincident dot patterns. The human eye resolves two colored dots side by side as one colored dot that is a blend of the two. The eye is more sensitive to lightness variations than to colorfulness or hue variations. In lightly tinted regions, dot distributions of multiple colors that are jointly uniformly spatially distributed will produce more total dots per square inch and result in a less grainy appearance than is produced by coincident dot patterns that result in the same visual lightness. Furthermore, coincident dot patterns use subtractive mixture to produce secondary colors, and this process results in lower lightness and lower colorfulness than is obtained with the additive mixture that occurs when dots are side by side.
If in a color printing system, identical CMY (K) error diffusers having identical seed values are run independently of each other, and if in the first part of the printed image, any two or more of the color primaries happen to have equal tint levels, then the dot patterns generated for said primaries will be coincident. Therefore, a method is needed that manipulates the seed values to avoid objectionable artifacts in digital printed images.